#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 2008;
int t,k;
int n,m;
int ans;
int vis[maxn][maxn];

void build()
{
    //创建组合数
    vis[0][0] = 1;
    vis[1][0] = vis[1][1] = 1;
    for(int i=2;i<=2000;i++)
    {
        vis[i][0] = 1;
        for(int j=1;j<=2000;j++)
        {
            vis[i][j] = vis[i-1][j-1]+vis[i-1][j]; //递推公式
        }
    }

}

void solve()
{
    cin >> n >> m;
    ans = 0;
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=min(i,m);j++)
        {
            if(vis[i][j]%k==0)
                ans++;
        }
    }
    cout << ans << endl;
}

void coutVis()
{
    for(int i=0;i<20;i++)
    {
        for(int j=0;k<20;j++)
        {
            cout << vis[i][j] << ' ';
        }
        cout << endl;
    }
}

int main()
{
    build();
    cin >> t >> k;
    while(t--)
    {
        solve();
    }
    return 0;
}